package com.xgh.niuke.mietuan;

import java.math.BigInteger;

/**
 * @ClassName MeiTuan1
 * @Description
 * @Author xinggh
 * @Date 2020/8/8 11:36
 * @Version 1.0
 **/
public class MeiTuan1 {
    /**
     * 题目描述
     * 有一个长为n的数组A，求满足0≤a≤b<n的A[b]-A[a]的最大值。
     * <p>
     * 给定数组A及它的大小n，请返回最大差值。
     * <p>
     * 测试样例：
     * [10,5],2
     * 返回：0
     *
     * @param A
     * @param n
     * @return
     */
    public int getDis(int[] A, int n) {

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                result = Math.max(result, A[i] - A[i]);
            }
        }
        return result;
    }

    /**
     * 有一个直方图，用一个整数数组表示，其中每列的宽度为1，求所给直方图包含的最大矩形面积。比如，对于直方图[2,7,9,4],它所包含的最大矩形的面积为14(即[7,9]包涵的7x2的矩形)。
     * <p>
     * 给定一个直方图A及它的总宽度n，请返回最大矩形面积。保证直方图宽度小于等于500。保证结果在int范围内。
     * <p>
     * 测试样例：
     * [2,7,9,4,1],5
     */

    public static int countArea(int[] A, int n) {
        // write code here

        int maxArea = 0;
        for (int i = 0; i < A.length; i++) {

            int hight = A[i];
            for (int j = i; j < A.length; j++) {
                hight = Math.min(hight, A[j]);
                int weight = i == j ? 1 : (j - i + 1);
                System.out.println(hight + "*" + weight + " =" + hight * weight);
                maxArea = Math.max(maxArea, hight * weight);
            }
        }
        return maxArea;
    }


    /**
     * 题目描述
     * 现在有一个数组，其值为从1到10000的连续增长的数字。出于某次偶然操作，
     * 导致这个数组中丢失了某三个元素，同时顺序被打乱，现在需要你用最快的方法找出丢失的这三个元素，
     * 并且将这三个元素根据从小到大重新拼接为一个新数字，计算其除以7的余数。
     * 例：丢失的元素为336，10，8435，得到的新数字为103368435，除以七的余数为2。
     *
     * @param args
     */

    public int method(int[] a) {
        int[] numarr = new int[10001];
        int[] input = new int[9997];
        for (int i = 0; i < numarr.length; i++) {
            numarr[input[i]] = 1;
        }

        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < numarr.length; i++) {
            if (numarr[i] == 0) {
                stringBuilder.append(i);
            }
        }
        BigInteger l = new BigInteger(stringBuilder.toString());
        //return l % 7;
        return 1;
        //   System.out.println(l % 7);

    }

    public static int uniquePaths(int m, int n) {
        int[][] dp = new int[11][11];
        for (int i = 0; i <= n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    public static long count(int n){
        if(n<=0) return 0;
        long[] dp = new long[n+1];
        dp[0] = 1;
        //这里int[]千万不要少了[]这个括号....
        int[]coins = new int[]{1,5,10,20,50,100};
        for(int i = 0;i<coins.length;i++){
            for(int j = coins[i];j<=n;j++){
                dp[j] = dp[j]+dp[j-coins[i]];
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
       /* int[] a = {281, 179, 386, 165, 88, 500};
        System.out.println(countArea(a, 6));*/
      //  System.out.println(uniquePaths(3, 2));
        System.out.println(count(11));
    }
}
